{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Factorial Zeros LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trailingZeroes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #阶乘尾数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设计一个算法，算出 n 阶乘有多少个尾随零。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> 3\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>&nbsp;3! = 6, 尾数中没有零。</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> 5\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong>&nbsp;5! = 120, 尾数中有 1 个零.</pre>\n",
    "\n",
    "<p><strong>说明: </strong>你算法的时间复杂度应为&nbsp;<em>O</em>(log&nbsp;<em>n</em>)<em>&nbsp;</em>。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [factorial-zeros-lcci](https://leetcode.cn/problems/factorial-zeros-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [factorial-zeros-lcci](https://leetcode.cn/problems/factorial-zeros-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        m = 0\n",
    "        while n > 0:\n",
    "            m += n//5\n",
    "            n = n//5\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "        else:\n",
    "            res = 0\n",
    "            i = 1\n",
    "            fives = []\n",
    "            for s in range(1, n+1):\n",
    "                if s == 5**i:\n",
    "                    res += i\n",
    "                    i += 1\n",
    "                    fives.append(s)\n",
    "                else:\n",
    "                    if str(s)[-1] in ['0', '5']:\n",
    "                        for j, x in enumerate(fives[::-1]):\n",
    "                            if s%x==0:\n",
    "                                res += len(fives)-j\n",
    "                                break\n",
    "            return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 1\n",
    "        res = 0\n",
    "        for i in range(1,n+1):\n",
    "            count = count * i\n",
    "        \n",
    "        count = list(str(count))\n",
    "        for i in count[::-1]:\n",
    "            if i =='0':\n",
    "                res = res + 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        amount = 0\n",
    "        for i in range(1, n+1):\n",
    "            while i % 5 == 0:\n",
    "                amount += 1\n",
    "                i /= 5\n",
    "        return amount "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        o = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            c = i\n",
    "            while c % 5 == 0:\n",
    "                c /= 5\n",
    "                o += 1 \n",
    "\n",
    "        return o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res=0\n",
    "        num=1\n",
    "        for i in range(1,n+1):\n",
    "            num*=i\n",
    "        num=list(map(int,str(num)))\n",
    "        for i in num[::-1]:\n",
    "            if i==0:\n",
    "                res+=1\n",
    "            if i!=0:\n",
    "                break\n",
    "        return res\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5,n+1,5):\n",
    "            while i%5==0:\n",
    "                i//=5\n",
    "                ans+=1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        import math\n",
    "        result=0\n",
    "        for i in range(1,n+1):\n",
    "            if i%5 == 0:\n",
    "                while i>=5 and i%5==0:\n",
    "                    result=result+1\n",
    "                    i = i/5\n",
    "            else:\n",
    "                continue        \n",
    "        return int(result)            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "\n",
    "        while n:\n",
    "            n //= 5\n",
    "            cnt += n\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        two_count = 0\n",
    "        five_count = 0\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        for i in range(1, n + 1):\n",
    "            while i and i % 2 == 0:\n",
    "                # print('2:' + str(i))\n",
    "                two_count += 1\n",
    "                i //= 2\n",
    "            while i and i % 5 == 0:\n",
    "                # print('5:' + str(i))\n",
    "                five_count += 1\n",
    "                i //= 5\n",
    "        return min(two_count, five_count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        x = 0\n",
    "        for i in range(1,n+1):\n",
    "            a = i\n",
    "            while a % 5 == 0:\n",
    "                a = a / 5\n",
    "                x += 1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n<5:\n",
    "            return 0\n",
    "        \n",
    "        result=0\n",
    "        while n>=5:\n",
    "            result+=n//5\n",
    "            n=n//5\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        #  find 5 的个数:\n",
    "        rt = 0\n",
    "        for i in range(1,n+1):\n",
    "            while (i%5==0):\n",
    "                i = i/5\n",
    "                rt+=1\n",
    "        return rt \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        zerocnt = 0\n",
    "        for i in range(5,n+1,5):\n",
    "            temp = i\n",
    "            while temp % 5 ==0:\n",
    "                zerocnt+=1\n",
    "                temp = temp // 5\n",
    "        return zerocnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        carry = 1\n",
    "        max_length = len(str(n)) + 1\n",
    "        for i in range(1, n + 1):\n",
    "            carry *= i\n",
    "            while carry % 10 == 0:\n",
    "                res += 1\n",
    "                carry //= 10\n",
    "            carry = int(str(carry)[-max_length:])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # count = len(list(filter(lambda x: x % 5 == 0, range(1, n+1))))\n",
    "        count = 0\n",
    "        while(n>=5):\n",
    "            count += n //5\n",
    "            n = n // 5\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        while n >= 5:\n",
    "            res += n // 5\n",
    "            n //= 5\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n // 5 > 0:\n",
    "            res = res + n // 5\n",
    "            n //= 5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        sum0=0\n",
    "        while n>=5:\n",
    "            n=n//5\n",
    "            sum0+=n\n",
    "        return sum0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return int(n/5)+int(n/25)+int(n/125)+int(n/625)+int(n/3125)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n < 5:\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            ans += n\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trailingZeroes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # 0 来源于10的个数，10=2*5，2的个数远大于5，所以只需要计算5、5的n次方的个数\n",
    "        # n/5 + n/25 + n/125 + ...\n",
    "\n",
    "        res = 0\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            res += n\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            n = int(n/5)\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return sum(n // 5 ** i for i in range(1, 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            res += n\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trailingZeroes(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        i = 5\n",
    "        while n >= i:\n",
    "            count += n // i\n",
    "            i *= 5\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        while n:\n",
    "            n//=5\n",
    "            ans+=n\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "\n",
    "        r = 0\n",
    "        while n>=5:\n",
    "            r+=n//5\n",
    "            n=n//5\n",
    "        return r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        i = 5\n",
    "        while n // i > 0:\n",
    "            count += n // i\n",
    "            i *= 5\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans =0\n",
    "        while n>=5:\n",
    "            ans += n//5\n",
    "            n = n//5\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(0,n+1,5):\n",
    "            t = i\n",
    "            while t%5==0 and t>0:\n",
    "                t/=5\n",
    "                cnt+=1\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ret = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            ret += n\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n//5>0:\n",
    "            res+=n//5\n",
    "            n=n//5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        def fac(x):\n",
    "            c = 0\n",
    "            while x > 0 and x % 5 == 0:\n",
    "                c += 1\n",
    "                x = x // 5\n",
    "            return c\n",
    "        f5 = 0\n",
    "        for z in range(1, n + 1):\n",
    "            f5 += fac(z)\n",
    "        return f5\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n+1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i = i // 5\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        i=5\n",
    "        count=0\n",
    "        while n//i: \n",
    "            count+=n//i\n",
    "            i*=5\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            ans += n//5\n",
    "            n //= 5\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count=0\n",
    "\n",
    "        while n>=5:\n",
    "            count+=n//5\n",
    "            n//=5\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return n // 5 + n // 25 + n // 125 + n // 625 + n // 3125"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def trailingZeroes(self, n: int) -> int:\n",
    "    ans = 0\n",
    "    while n:\n",
    "      n //= 5\n",
    "      ans += n\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        result = 0\n",
    "        for i in range(1, n + 1):\n",
    "            tmp = i\n",
    "            while tmp % 5 == 0:\n",
    "                tmp /= 5\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            res += n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return n//5+n//25+n//125+n//625+n//3125"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0 \n",
    "        while n >=5:\n",
    "            n = n // 5\n",
    "            res += n \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return n // 5 + self.trailingZeroes(n // 5) if n // 5 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return n // 5 + self.trailingZeroes(n // 5) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt=0\n",
    "        while n>0:\n",
    "            n //= 5\n",
    "            cnt += n\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        t=0\n",
    "        while n:\n",
    "            n//=5\n",
    "            t+=n\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "\n",
    "        count = 0 \n",
    "        \n",
    "        for i in range(5, n+1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5  # replace i with i // 5\n",
    "                count += 1\n",
    "\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n>=5:\n",
    "            count += int(n / 5);\n",
    "            n = n / 5;\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(5, n + 1, 5):\n",
    "            while i % 5 == 0:\n",
    "                i //= 5\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        p = 0\n",
    "        while n >= 5:\n",
    "            n = n // 5\n",
    "            p += n\n",
    "        return p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        fac = math.factorial(n)\n",
    "        res = 0\n",
    "        while fac % 10 == 0:\n",
    "            res += 1\n",
    "            fac //= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0 \n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            res += n \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        while n:\n",
    "            n//=5\n",
    "            ans+=n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,6):\n",
    "            if n // (5**i) == 0:\n",
    "                break\n",
    "            res += n // (5**i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # 5! = 120, 有 1 个 0\n",
    "        # 不能直接阶乘是因为有溢出的可能性\n",
    "        # 所以就要找到什么情况才会产生 0\n",
    "        # 解题：对于阶乘过程的每个数，[1, n]，寻找质因数对 {2, 5} 的个数\n",
    "\n",
    "        def fac(x, y):\n",
    "            cnt = 0\n",
    "            while x > 0 and x % y == 0:\n",
    "                cnt += 1\n",
    "                x /= y\n",
    "            return cnt\n",
    "\n",
    "        cnt_2 = 0\n",
    "        cnt_5 = 0\n",
    "        for k in range(1, n+1):\n",
    "            cnt_2 += fac(k, 2)\n",
    "            cnt_5 += fac(k, 5)\n",
    "\n",
    "        return min(cnt_2, cnt_5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        divisor = 5\n",
    "\n",
    "        while n >= divisor:\n",
    "            res += n // divisor\n",
    "            divisor *= 5\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        def fac(x, y):\n",
    "            c = 0\n",
    "            while x > 0 and x % y == 0:\n",
    "                c += 1\n",
    "                x /= y\n",
    "            return c\n",
    "        f2, f5 = 0, 0\n",
    "        for z in range(1, n + 1):\n",
    "            f2 += fac(z, 2)\n",
    "            f5 += fac(z, 5)\n",
    "        return f5\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n//5:\n",
    "            res += n//5\n",
    "            n = n//5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        r = 0\n",
    "        for i in range(5, n+1, 5):\n",
    "            while i%5 ==0:\n",
    "                i //= 5\n",
    "                r += 1\n",
    "        return r \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        i = 5\n",
    "        while n // i >= 1:\n",
    "            count += n//i\n",
    "            i = i * 5\n",
    "        return count \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        def fac(x, y):\n",
    "            c = 0\n",
    "            while x > 0 and x % y == 0:\n",
    "                c += 1\n",
    "                x /= y\n",
    "            return c\n",
    "        f5 = 0\n",
    "        for z in range(1, n + 1):\n",
    "\n",
    "            f5 += fac(z, 5)\n",
    "        return f5\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count  = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n // 5:\n",
    "            ans += n // 5\n",
    "            n //= 5\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        k = 5\n",
    "        while n >= k:\n",
    "            res += n // k\n",
    "            k *= 5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        while n>=5:\n",
    "            n=n//5\n",
    "            ans+=n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        return n // 5 + n // 25 + n // 125 + n // 625 + n // 3125 +  n // 15625 + n // 78125 + n // 390625 + n // 1953125 +  n // 9765625 + n // 48828125 + n // 244140625 + n // 1220703125\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        a = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            a += n\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        return count\n",
    "\n",
    "\n",
    "        # dp = [0] * (n+1)\n",
    "        # dp[0] = 1\n",
    "        # dp[1] = 1\n",
    "        # for i in range(2, n+1):\n",
    "        #     dp[i] = i * dp[i-1] \n",
    "        # my_str = str(dp[n])\n",
    "        # right = len(my_str)\n",
    "        # while right > 0:\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt=0\n",
    "        while n>=5:\n",
    "            n=n//5\n",
    "            cnt=cnt+n\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        i=1\n",
    "        ans=0\n",
    "        while i>0:\n",
    "            if 5**i>n:\n",
    "                break\n",
    "            i+=1\n",
    "        for j in range(1,i):\n",
    "            ans+=(n//(5**j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # exact same as a lc medium\n",
    "    # basically just need number of factors of 2,5\n",
    "    # min of the 2\n",
    "    # there are more factors of 2 than 5\n",
    "    # 5,10,15,20,30,... all have 1 factor of 5\n",
    "    # 25,50,75 all have 2 factors of 5\n",
    "    # 125,625 all have 3 factors of 5\n",
    "    # ...\n",
    "\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0: return 0\n",
    "        return n // 5 + self.trailingZeroes(n//5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            cnt += n\n",
    "        return cnt\n",
    "'''\n",
    "         0 是由 *10 得到的，而 10 是由 2 * 5 得到的\n",
    "         因此我们求 n！ 过程中存在多少个 2 * 5\n",
    "         因为 2 的个数必定比 5 的个数多，因此我们只求 5 的个数\n",
    "\n",
    "         如果直接一个一个遍历，即 \n",
    "         for(int i = 5; i <= n; i++){\n",
    "            int temp = i;\n",
    "            while(temp % 5 == 0){\n",
    "                count++;\n",
    "                temp /= 5;\n",
    "            }\n",
    "        }\n",
    "        那么 n 过大时，从 1 遍历到 n, 那么会超时,因此我们修改下规律\n",
    "\n",
    "        n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) ...\n",
    "        我们发现，\n",
    "        每隔 5 个数就会出现 一个 5，因此我们只需要通过 n / 5 来计算存在存在多少个 5 个数，那么就对应的存在多少个 5\n",
    "        但是，我们也会发现\n",
    "        每隔 25 个数会出现 一个 25， 而 25 存在 两个 5，我们上面只计算了 25 的一个 5，因此我们需要 n / 25 来计算存在多少个 25，加上它遗漏的 5\n",
    "        同时，我们还会发现\n",
    "        每隔 125 个数会出现一个 125，而 125 存在 三个 5，我们上面只计算了 125 的两个 5，因此我们需要 n / 125 来计算存在多少个 125，加上它遗漏的 5\n",
    "        ...\n",
    "\n",
    "        因此我们 count = n / 5 + n / 25 + n / 125 + ...\n",
    "        最终分母可能过大溢出，上面的式子可以进行转换\n",
    "\n",
    "        count = n / 5 + n / 5 / 5 + n / 5 / 5 / 5 + ...\n",
    "        因此，我们这样进行循环\n",
    "        n /= 5;\n",
    "        count += n;\n",
    "        这样，第一次加上的就是 每隔 5 个数的 5 的个数，第二次加上的就是 每隔 25 个数的 5 的个数 ...\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        while n > 0:\n",
    "\n",
    "            n = n // 5\n",
    "            cnt += n\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count = count + n\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # 尾随0的个数 = （2*5）的因子个数 = 5的因子个数（2的因子个数显然远大于5）\n",
    "        # 5的因子个数 = 5的倍数个数 + 25的倍数个数 + 125的倍数个数 + ...\n",
    "        # if n <= 4: return 0\n",
    "        cnt = 0\n",
    "        powers = 5\n",
    "        while powers <= n:\n",
    "            cnt += (n // powers)\n",
    "            powers *= 5\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count\n",
    "\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            n = n // 5 # numbers of 5 may be more than 2\n",
    "            res += n \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            count += n\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            res += n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        temp=5\n",
    "        while n>=temp:\n",
    "            ans+=n//temp\n",
    "            temp*=5\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n >= 5:\n",
    "            n //= 5 #计算有多少个5\n",
    "            count += n\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        while n:\n",
    "            n//=5\n",
    "            ans+=n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        cnt=0\n",
    "        while n>0:\n",
    "            n//=5\n",
    "            cnt+=n\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res=0\n",
    "        while n>1:\n",
    "            res+=n//5\n",
    "            n=n//5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            ans += n // 5\n",
    "            n //= 5\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count=0\n",
    "        while n:\n",
    "            count+=n//5\n",
    "            n//=5\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n>0:\n",
    "            n //= 5 \n",
    "            res += n \n",
    "            \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans=0\n",
    "        while n:\n",
    "            n//=5\n",
    "            ans+=n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            ans += n // 5\n",
    "            n //= 5\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        zeros = 0\n",
    "        fives = 5\n",
    "        while fives <= n:\n",
    "            zeros += n // fives\n",
    "            fives *= 5\n",
    "        \n",
    "        return zeros"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            res += n\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        \n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0 :\n",
    "            n //= 5\n",
    "            count += n\n",
    "        return count\n",
    "\n",
    "        # dp = [0] * (n+1)\n",
    "        # dp[0] = 1\n",
    "        # dp[1] = 1\n",
    "        # for i in range(2, n+1):\n",
    "        #     dp[i] = i * dp[i-1] \n",
    "        # my_str = str(dp[n])\n",
    "        # right = len(my_str)\n",
    "        # while right > 0:\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n < 5:\n",
    "            return 0\n",
    "        else:\n",
    "            return n // 5 + self.trailingZeroes(n//5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n>0:\n",
    "            n //= 5 \n",
    "            res += n \n",
    "            \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while(n):\n",
    "            n = n //5\n",
    "            count += n\n",
    "        \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        #能被多少个10(2,5)整除\n",
    "       #fn-1 的个数 和n被10乘的个数\n",
    "            ans=0\n",
    "            while n:\n",
    "                n//=5\n",
    "                ans+=n\n",
    "            return ans\n",
    "                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def trailingZeroes(self, n: int) -> int:\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            count = 0\n",
    "            while n > 0:\n",
    "                n = n // 5\n",
    "                count += n\n",
    "            return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # 尾随0的个数 = （2*5）的因子个数 = 5的因子个数（2的因子个数显然远大于5）\n",
    "        # if n <= 4: return 0\n",
    "        cnt = 0\n",
    "        powers = 5\n",
    "        while powers <= n:\n",
    "            cnt += (n // powers)\n",
    "            powers *= 5\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n>0:\n",
    "            n //= 5 \n",
    "            res += n \n",
    "            \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        # 质因数2的个数一定比5多，所以有几个5，后面就有几个0\n",
    "        # 然后一次找5的倍数，25的倍数，125的倍数\n",
    "        t = 5\n",
    "        ans = 0\n",
    "        while t <= n:\n",
    "            ans += n // t\n",
    "            t *= 5\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        base = 5 \n",
    "        total = 0 \n",
    "\n",
    "        while base <= n: \n",
    "            total += n // base \n",
    "            base *= 5 \n",
    "        return total "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n > 1:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        #能被多少个10(2,5)整除\n",
    "       #fn-1 的个数 和n被10乘的个数\n",
    "            ans=0\n",
    "            while n:\n",
    "                n//=5\n",
    "                ans+=n\n",
    "            return ans\n",
    "                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            res+=n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n > 1:\n",
    "            res += n // 5\n",
    "            n = n // 5\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        def count_zero_behind(n):\n",
    "            a  = int(n/5)\n",
    "            if a == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return a + count_zero_behind(a)\n",
    "        return count_zero_behind(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        cnt=0\n",
    "        while n>0:\n",
    "            n=n//5\n",
    "            cnt+=n\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            ans += n\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            res+=n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        a = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            a += n\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n // 5 > 0:\n",
    "            count += n // 5\n",
    "            n //= 5\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while(n):\n",
    "            n = n //5\n",
    "            count += n\n",
    "        \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res=0\n",
    "        while n>1:\n",
    "            res+=n//5\n",
    "            n=n//5\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res=0\n",
    "        while n>1:\n",
    "            res+=n//5\n",
    "            n=n//5\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "         0 是由 *10 得到的，而 10 是由 2 * 5 得到的\n",
    "         因此我们求 n！ 过程中存在多少个 2 * 5\n",
    "         因为 2 的个数必定比 5 的个数多(比如4、8等都是2组成的)，因此我们只求 5 的个数\n",
    "\n",
    "         如果直接一个一个遍历，即:\n",
    "\n",
    "         for i in range(n):\n",
    "             tmp = i\n",
    "             while tmp % 5 == 0:\n",
    "                 cnt += 1\n",
    "                 tmp //= 5\n",
    "\n",
    "        那么 n 过大时，从 1 遍历到 n, 那么会超时,因此我们修改下规律\n",
    "\n",
    "        n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) ...\n",
    "        我们发现，\n",
    "        每隔 5 个数就会出现 一个 5，因此我们只需要通过 n / 5 来计算存在存在多少个 5 个数，那么就对应的存在多少个 5\n",
    "        但是，我们也会发现\n",
    "        每隔 25 个数会出现 一个 25， 而 25 存在 两个 5，我们上面只计算了 25 的一个 5，因此我们需要 n / 25 来计算存在多少个 25，加上它遗漏的 5\n",
    "        同时，我们还会发现\n",
    "        每隔 125 个数会出现一个 125，而 125 存在 三个 5，我们上面只计算了 125 的两个 5，因此我们需要 n / 125 来计算存在多少个 125，加上它遗漏的 5\n",
    "        ...\n",
    "\n",
    "        因此我们 count = n / 5 + n / 25 + n / 125 + ...\n",
    "        最终分母可能过大溢出，上面的式子可以进行转换\n",
    "\n",
    "        count = n / 5 + n / 5 / 5 + n / 5 / 5 / 5 + ...\n",
    "        因此，我们这样进行循环\n",
    "        n /= 5;\n",
    "        count += n;\n",
    "        这样，第一次加上的就是 每隔 5 个数的 5 的个数，第二次加上的就是 每隔 25 个数的 5 的个数 ...\n",
    "        \"\"\"\n",
    "\n",
    "        cnt = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            cnt += n\n",
    "            \n",
    "        return cnt\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        count = 0\n",
    "        while n > 0:\n",
    "            n = n // 5\n",
    "            count += n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n >= 5:\n",
    "            n //= 5\n",
    "            res += n\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
